package cn.z2huo.algorithm.binarytree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

// 层次遍历一棵二叉树，输出结果为列表，例如 [[1], [2,3], [4,5], [6,7]]，其中子列表表示树的一个层次
public class Traversal_levelOrder {
    public List<List<Integer>> levelOrder(TreeNode root){
        if (root==null){
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new ArrayList<>();

        queue.offer(root);
        while (!queue.isEmpty()){
            int count = queue.size();
            List<Integer> list = new ArrayList<>();
            while (count>0){
                TreeNode node = queue.poll();
                list.add(node.getValue());
                if (node.getLeft()!=null)   queue.offer(node.getLeft());
                if (node.getRight()!=null)  queue.offer(node.getRight());
                count --;
            }
            result.add(list);
        }
        return result;
    }

    public static void main(String[] args){
        BinaryTree bt = new BinaryTree();
        int[] array = {1,2,3,4,5,0,0,0,0,6,7};
//        int[] array = {};
        TreeNode root = bt.createTree(array);

        Traversal_levelOrder tl = new Traversal_levelOrder();
        List<List<Integer>> list = tl.levelOrder(root);
        for (List<Integer> l : list){
           for (Integer i : l){
               System.out.print(i+" ");
           }
           System.out.println();
        }
    }
}